package SinglyList;

import java.util.HashMap;
import java.util.Map;

public class SinglyList<E> implements LinearList<E>{
	public Node<E> head;
	public int size;					

	public SinglyList() {
		head = new Node<E>();
		size = 0;
	}

	public SinglyList(E[] values) {
		this();
		Node<E> last = head;
		for (E value : values) {
			last.next = new Node<>(value, null);
			last = last.next;
		}
		size = values.length;
	}
	
	@Override
	public boolean isEmpty() {
		return head.next == null;
	}

	@Override
	public int size() {
		return size;
	}

	//将指针移动到目前你所需要处理的结点的前驱
	public Node<E> getLocation(int i){

		//此时指针会移动到链表之外
		if (i-1>size)throw new ArrayIndexOutOfBoundsException("数组下标越界了");

		//此时指针会处于链表之外
		if (i<=0)return null;

		//进行循环移动到第 i 个节点的前驱
		int cur=0;
		Node<E> loc=head;
		while (cur<(i-1)){
			loc=loc.next;
			cur++;
		}
		return loc;
	}

	//通过下标索引号获取某个节点
	@Override
	public E get(int i) {
		//TODO
		if (i<=size){
			Node<E> temp = head.next;
			int cur = 1;
			while (cur!=i){
				temp = temp.next;
				cur++;
			}
			return (i>=0&&temp!=null)?temp.data:null;
		}
		return null;
	}

	//设置某个索引号结点的值
	@Override
	public void set(int i, E x) {
		//TODO
		Node<E> location = this.getLocation(i+1);
		if (location!=null){
			location.data=x;
		}else throw new NullPointerException();
	}

	//在第 i 个位置插入数据为 x 的结点
	@Override
	public boolean insert(int i, E x) {
		if (x!=null){
			Node<E> location = this.getLocation(i);
			Node<E> cur = new Node<>(x,null);
			if (location.next==null){
				location.next=cur;
				return true;
			}
			cur.next=location.next;
			location.next=cur;
			size++;
			return true;
		}else return false;
	}

	//通过构造函数在末尾插入元素
	@Override
	public int insert(E x) {
		insert(++size,x);
		return size;
	}

	//通过索引号 i 移除第 i 个结点
	@Override
	public E remove(int i) {
		// TODO
		Node<E> location = this.getLocation(i);
		E data = location.next.data;
		location.next=location.next.next;
		size--;
		return data;
	}

	//清空全部节点
	@Override
	public void clear() {
		head.next = null;
	}

	//查找数据为 key 的第一次出现的地方
	@Override
	public int search(E key) {
		// TODO
		int i =2;
		while (i<=size){
			if (this.getLocation(i).data.equals(key))return i-1;
			else i++;
		}
		return -1;
		
	}

	//查看链表中是否包含 key
	@Override
	public boolean contains(E key) {
		int i = search(key);
		return i!=-1;
	}

	//移除第一次出现的结点
	@Override
	public int remove(E key) {
		int i = search(key);
		remove(i);
		return i;
	}

	//打印输出
	public String toString() {
		String str = "[";
		Node<E> p =head.next;
		if (p!=null){
			str += p.data.toString();
			p=p.next;
		}
		while (p!=null) {
			str += ","+p.data.toString();
			p = p.next;
		}
		return str + "] ";
	}

	public void reverse(){
		Node<E> cur = this.getLocation(size+1);
		Node<E> fin = this.getLocation(size+1);
		Node<E> nextnode = this.getLocation(size);
		for (int i = size;i>1;i--){
			cur.next=nextnode;
			nextnode.next=null;
			cur = nextnode;
			nextnode=this.getLocation(i-1);
		}
		head.next=fin;
	}

	//返回p结点的前驱结点
	public Node<E> prev(Node<E> p){
		Node<E> cur = head.next;
		while (cur.next!=p){
			cur = cur.next;
			if(cur.next==null){
				throw new NullPointerException("该节点不存在于单链表中");
			}
		}
		return cur;
	}

	//返回最后一个结点
	public Node<E> last(){
		Node<E> cur = head.next;
		while (cur.next!=null){
			cur=cur.next;
		}
		return cur;
	}
	
	//返回从第i个结点开始，长度为len的子表，深拷贝
	public SinglyList<E> subList(int i,int len){
		Node<E> location = this.getLocation(i+1);

		E[] source = (E[]) new Object[len];
		for (int j=0;j<len;j++){
			source[j] = location.data;
			location = location.next;
		}
		return new SinglyList<>(source);
	}

	public void partition(SinglyList<Integer> list,int l,int r){
		if (l>r)return;
		int left = l;
		int right = r;
		Node<Integer> start = list.getLocation(left+1);
		Node<Integer> end = list.getLocation(right+1);
		int pivot = start.data;
		int count= 1;
		while (start!=end){
			while (start!=end&&end.data>=pivot){
				end = list.prev(end);
			}
			start.data = end.data;
			while (start!=end&&start.data<=pivot){
				start = start.next;
				count++;
			}
			end.data = start.data;
		}
		start.data = pivot;
		if (r>left)partition(list,left,r-1);
		if (right>l)partition(list,l+1,right);
	}

	public void removeAll(SinglyList<E> list){
		Map<E, Integer> hashmap = new HashMap<>();
		Node<E> cur = list.head;
		while (cur.next!=null){
			hashmap.put(cur.data,1);
			cur = cur.next;
		}
		cur = this.head;
		while (cur.next!=null){
			if (hashmap.containsKey(cur.data))hashmap.put(cur.data,2);
			cur=cur.next;
		}
		cur = this.head;
		while (cur.next!=null&&cur.next.next!=null){
			Node<E> temp = cur.next;
			if (hashmap.containsKey(temp.data)&&hashmap.get(temp.data)==2){
				cur.next=cur.next.next;
			}
			else cur=cur.next;
		}
		if (hashmap.containsKey(cur.next.data)&&hashmap.get(cur.next.data)==2)cur.next=null;
	}


	public SinglyList<E> difference(SinglyList<E> list){
		Map<E, Integer> hashmap = new HashMap<>();
		Node<E> cur = list.head;
		while (cur.next!=null){
			hashmap.put(cur.data,1);
			cur = cur.next;
		}
		cur = this.head;
		while (cur.next!=null){
			if (hashmap.containsKey(cur.data))hashmap.put(cur.data,2);
			cur=cur.next;
		}
		SinglyList<E> result = new SinglyList<E>();
		cur = this.head;
		while (cur.next!=null){
			
		}
		return result;
	}
}